至少有一半不小于 , 至少有一半不大于
所以 应该是选出的区域人口的中位数。
为了使误差尽可能小，每次应该取排序后连续的一段区间染相同颜色。
令 表示使用前 种颜色，将前 个区域染色的最小误差， 表示将 染成一个颜色的误差。
那么有：
可以分类讨论中位数的值，分成 小于中位数 和 大于中位数 两种情况计算。
这道题中位数好像取不取小数都能过。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 3000 , MAXM = 10;
int n , m , a[ MAXN + 5 ];
LL Suma[ MAXN + 5 ]; double dp[ MAXM + 5 ][ MAXN + 5 ];
double Val( int l , int r ) {
int Mid = ( l + r ) >> 1;
if( ( r - l + 1 ) % 2 ) { //l Mid r
double Mida = a[ Mid ];
return ( Suma[ r ] - Suma[ Mid - 1 ] - Mida * ( r - Mid + 1 ) ) + ( Mida * ( Mid - l ) - ( Suma[ Mid - 1 ] - Suma[ l - 1 ] ) );
}
else { //l Mid Mid+1 r
double Mida = ( a[ Mid ] + a[ Mid + 1 ] ) / 2.0;
return ( Suma[ r ] - Suma[ Mid ] - Mida * ( r - Mid ) + Mida * ( Mid - l + 1 ) - ( Suma[ Mid ] - Suma[ l - 1 ] ) );
}
}
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i ++ ) scanf("%d", &a[ i ] );
sort( a + 1 , a + n + 1 );
for( int i = 1 ; i <= n ; i ++ ) Suma[ i ] = Suma[ i - 1 ] + a[ i ];
for( int i = 0 ; i <= m ; i ++ ) for( int j = 0 ; j <= n ; j ++ ) dp[ i ][ j ] = 1e15;
dp[ 0 ][ 0 ] = 0;
for( int i = 1 ; i <= m ; i ++ )
for( int j = 1 ; j <= n ; j ++ )
for( int k = 1 ; k <= j ; k ++ )
dp[ i ][ j ] = min( dp[ i ][ j ] , dp[ i - 1 ][ k - 1 ] + Val( k , j ) );
printf("%.0f\n", dp[ m ][ n ] );
return 0;
}
